class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.len = capacity
        self.queue = []
        self.map = {}


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.map:
            self.queue.remove(key)
            self.queue.append(key)
            return self.map[key]
        else:
            return -1


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.map:
            self.map[key] = value
            self.queue.remove(key)
            self.queue.append(key)
        else:
            if len(self.queue) == self.len:
                remove_key = self.queue.pop(0)
                del self.map[remove_key]
            self.queue.append(key)
            self.map[key] = value
